33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
我们可以将其还原成一个有序数组，然后再做二分查找
还原成一个有序数组
解法1：
- 寻找最小值，逻辑分割成两个有序数组
- 依靠
nums[left]与target的大小关系，确定target在哪一个有序数组中 - 对可能存在
target的有序数组进行二分查找
解法2：
假设有个旋转数组 [5,6,7,1,2,3,4]
如果target在左边的升序数组中，则可以对 [5, 6 ,7 ,Inf, Inf, Inf]做二分查找
如果target在右边的升序数组中，则可以对[-inf, -inf, -inf, 1, 2, 3, 4]做二分查找
说明： inf 表示无穷
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
max_inf = float('inf')
min_inf = float('-inf')
while left <= right:
mid = (left + right) >> 1
if nums[mid] == target:
return mid
if nums[0] <= target:
# target在左边的升序数组中
# 如果此时mid位于右边，明显不符合，我们就将当前mid位置的值改为正无穷
if nums[0] > nums[mid]:
nums[mid] = max_inf
else:
# target在右边的升序数组中
if nums[0] <= nums[mid]
nums[mid] = min_inf
# 完成上述步骤，就可以开始做二分查找了
# 此时mid位置的值，不是正无穷，就是负无穷
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
直接使用二分查找
旋转数组可以看做是两个有序数组的拼接，并且右边的有序数组 整体小于 左边的有序数组
- 当
nums[mid] == target时，毫无疑问此时应该返回mid即可 - 当
nums[left] <= nums[mid]时
如果
target在区间[left ... mid]内，即满足nums[left] <= target <= nums[mid]反之，
target在mid右边的区间内，下一搜索区间就是[mid + 1 ... right]
- 当
nums[left] > nums[mid]时
此时
mid落在了右边有序数组中如果
target在区间[mid ... right]内，即满足nums[mid] <= target <= nums[right]反之，
target在mid左边的区间内，则下一搜索区间是[left ... mid - 1]
class Solution:
def search(self, nums: List[int], target: int) -> int:
length = len(nums)
left, right = 0, length - 1
while left <= right:
mid = (left + right) >> 1
if nums[mid] == target:
return mid
elif nums[left] <= nums[mid]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
34 搜索旋转排序数组 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
相比33题，这道题多了一个条件 nums 可能包含重复元素
所以可能出现这样的数组： [2,2,2,1,2]
在33题中，进行边界收缩依靠的是 nums[left] 与 nums[mid] 的关系，不是大于就是小于，我们可以清晰的判断并进行收缩
而在[2,2,2,1,2]这个数组中，nums[mid] 与 nums[left] 相等时，nums[right] 可能也是相等的，所以这就导致了，我们无法分辨mid目前所处位置，可能是左边也可能是右边
解决方法：当满足nums[left] == nums[mid]，将left向右收缩一位，直到不满足前面这个条件，然后就转换了33题。
class Solution:
def search(self, nums: List[int], target: int) -> bool:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) >> 1
if nums[mid] == target:
return True
elif nums[left] == nums[mid]:
left += 1
elif nums[mid] > target:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < target:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return False